#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#include "SeqList.h"

//初始化
void SeqListInit(SeqList* ps, int initCap)
{
    assert(ps); //判断ps的合法性(指针判空)

    //1.申请空间
    ps->array = (DataType*)malloc(initCap * sizeof(DataType));
    if(NULL == ps->array)
    {
        assert(0);
        return;
    }

    //2.将容量以及有效元素个数设置好
    ps->capacity = initCap;
    ps->size = 0;
}

//销毁
void SeqListDestroy(SeqList* ps)
{
    assert(ps);
    if(ps->array)
    {
        free(ps->array);
        ps->array = NULL; //释放掉之后必须将指针指向空  
        ps->capacity = 0; //容量也没有了
        ps->size = 0; //元素也没了
    }
}

//向顺序表中尾插data
void SeqListPushBack(SeqList* ps, DataType data)
{
    //1.当空间不够时需要扩容
    if(ps->size == ps->capacity)
    {
        SeqListReserve(ps, SeqListCapacity(ps) * 2);
    }
    //2.插入元素
    ps->array[ps->size++] = data; //原来共有size个元素，下标是0~(size-1),在size位置添加元素，然后再对size++
}

//将顺序表中最后一个元素删除掉
void SeqListPopBack(SeqList* ps)
{
    if(SeqListEmpty(ps)) //前提是不为空，才有元素删除
       return;

    ps->size--;
}

//在顺序表的pos位置插入元素data
void SeqListInsert(SeqList* ps, int pos, DataType data)
{
    assert(ps);

    if(pos < 0 || pos > ps->size) //插入元素的合法下标为 0 ~ size 
    {
        printf("位置非法！！！\n");
        return;
    }

    //检验空间是否足够
    if(ps->size == ps->capacity)
    {
        SeqListReserve(ps,SeqListCapacity(ps) * 2);
    }

    //插入
    //1.将pos位置以及后面位置的所有元素整体后移一位，从后往前搬移，从前往后会覆盖
    //i：表示要搬移的元素
    for(int i = ps->size-1; i >= pos; i--) 
    {
        ps->array[i + 1] = ps->array[i];
    }
    //第二种写法
    //i:表示要搬移到的位置
    //for(int i = ps->size; i > pos; i--)
    //{
    //  ps->array[i] = ps->array[i - 1]; //将size-1位置的元素移动到size位置
    //}
    
    //2.在pos位置插入元素
    ps->array[pos] = data;

    ps->size++; //有效元素的个数加1
}

//将顺序表中的pos位置的元素删除
void SeqListErase(SeqList*ps, int pos)
{
    assert(ps);

    if(pos < 0 || pos >= ps->size) //有效元素的合法下标为 0 ~ (size-1)
    {
        printf("pos位置非法！！！\n");
        return;
    }

    //1.搬移元素，从pos+1的位置开始搬(往前搬)
    for(int i = pos + 1; i < ps->size; i++) // i <= ps->size-1
    {
        ps->array[i - 1] = ps->array[i];
    }

    //2.删除
    ps->size--;
}

//获取有效元素的个数
int SeqListSize(SeqList* ps)
{
    assert(ps);
    return ps->size;
}

//获取顺序表的总容量 -- 底层空间的大小
int SeqListCapacity(SeqList* ps)
{
    assert(ps);
    return ps->capacity;
}

//检测顺序表是否为空
int SeqListEmpty(SeqList* ps)
{
    assert(ps);
    return 0 == ps->size;
}

//查找
int SeqListFind(SeqList* ps, DataType data)
{
    assert(ps);

    for(int i = 0; i < ps->size; i++)
    {
        if(data == ps->array[i])
            return i;
    }
    return -1;
}

//将顺序表中的容量扩增到Capacity
void SeqListReserve(SeqList* ps, int Capacity)
{
    assert(ps);

    if(Capacity <= ps->capacity)
        return;

    ps->array = (DataType*)realloc(ps->array,Capacity * sizeof(DataType));
    assert(ps->array);

    ps->capacity *= 2;
}

//测试方法
void SeqListPrint(SeqList* ps)
{
    assert(ps);

    for(int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->array[i]);
    }
    printf("\n");
}








